package sorting;
//https://leetcode.cn/leetbook/read/illustration-of-algorithm/p57uhr/

import java.util.Arrays;

/**
 * 快速排序算法有两个核心点，分别为 哨兵划分 和 递归 。
 *
 * 讨论一下为什么partition函数中，对于j和i的搜索顺序不能交换:
 * 首先明确一点，在partition的最后一步，我们将nums[ i ]和nums[ l ]交换了位置，
 * 即将最左节点放到了数组中间的某个位置，其左边元素比它都小，其右边元素比它都大。显然，最后一步的互换要求nums[ i ]比nums[ l ]更小。
 * 在明确了上面这个条件后，我们就很容易理解为什么在while内部对i和j进行移动操作时，必须先移动j，再移动i。
 * 如果我们先移动i的话，那就意味着当i停下来的时候，nums[ i ]指向的可能是比nums[ l ]更大的元素（因为i的循环条件是nums[ i ]<=nums[ l ]），
 * 这样我们在执行上面提到的交换操作时，就会造成节点左边存在比它更大元素的情况出现。
 *
 */
public class 快速排序 {
    public static void quickSort(int[] nums, int l, int r) {
        // 子数组长度为 1 时终止递归
        if (l >= r) return;
        // 哨兵划分操作
        int i = partition(nums, l, r);
        // 递归左（右）子数组执行哨兵划分
        quickSort(nums, l, i - 1);
        quickSort(nums, i + 1, r);
    }
    //尾递归优化
    private static void quickSort2(int[] nums, int l, int r) {
        // 子数组长度为 1 时终止递归
        while (l < r) {
            // 哨兵划分操作
            int i = partition(nums, l, r);
            // 仅递归至较短子数组，控制递归深度
            if (i - l < r - i) {
                quickSort(nums, l, i - 1);
                l = i + 1;
            } else {
                quickSort(nums, i + 1, r);
                r = i - 1;
            }
        }
    }

    public static int partition(int[] nums, int l, int r) {
        // 以 nums[l] 作为基准数
        int i = l, j = r;
        while (i < j) {
            while (i < j && nums[j] >= nums[l]) j--;
            while (i < j && nums[i] <= nums[l]) i++;
            swap(nums, i, j);
        }
        swap(nums, i, l);
        return i;
    }

    public static void swap(int[] nums, int i, int j) {
        // 交换 nums[i] 和 nums[j]
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    // 调用
    public static void main(String[] args) {
        int[] nums = { 4, 1, 3, 2, 5 ,7,6,9,10};
        quickSort(nums, 0,nums.length - 1);
        System.out.println("Sorted array: " + Arrays.toString(nums));

    }

}
